package offer.day35;

import java.util.*;

public class No59First_MaxInWindows {
    /*
     * 面试题59：队列的最大值
     * 题目一：滑动窗口的最大值
     * 给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。
     * 例如：如果输入数组{2，3，4，2，6，2，5}及滑动窗口的大小为3，那么一共存在6个滑动窗口，他们的最大值分别是{4，4，6，6，6，5}
     *
     *  * 例如：
     * 如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，
     * 他们的最大值分别为{4,4,6,6,6,5}；
     * 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个：
     * {[2, 3, 4], 2, 6, 2, 5, 1}，
     * {2, [3, 4, 2], 6, 2, 5, 1}，
     * {2, 3, [4, 2, 6], 2, 5, 1}，
     * {2, 3, 4, [2, 6, 2], 5, 1}，
     * {2, 3, 4, 2, [6, 2, 5], 1}，
     * {2, 3, 4, 2, 6, [2, 5, 1]}。
     *
     *
     *
     * 思路：运用双端队列，存储最大的下标+次大的下标，队头就是所要求的最大下标
     * 时间复杂度O(n)
     * 若当前值大于双端队列中存储的，则将其弹出  存储当前下标i
     * 然后再判断是否已经滑动窗口内的数量已经到达size，
     * 若表示队首元素是最大元素，但是要将队首元素出滑动窗口了，
     * 需要将其从队列中的队头出弹出，因为此最大值下标已经过期了呢
     * 然后再判断是否应该滑动窗口了，若i>size-1则表示需要滑动窗口，
     * 也就是自从第三个位置（也就是索引值为2的地方）开始就需要每一次都滑动窗口
     *
     * */
    public static void main(String[] args) {
        No59First_MaxInWindows m = new No59First_MaxInWindows();
        int[] array = {2, 3, 4, 2, 6, 2, 5};
        int size = 3;
        ArrayList<Integer> res = m.MaxInWindows(array, size);
        System.out.println("滑动窗口的最大值序列是：" + res);
    }

    private ArrayList<Integer> MaxInWindows(int[] array, int size) {
        ArrayList<Integer> res = new ArrayList<>();
        if (array == null || array.length == 0 || size == 0 || array.length < size) {
            return res;
        }
        Deque<Integer> vessel = new LinkedList<>();
        for(int i=0;i<array.length;i++){
            int cur=array[i];
            while(!vessel.isEmpty() && array[vessel.peekLast()]<=cur){
                vessel.pollLast();
            }
            vessel.offerLast(i);
            if(vessel.peekFirst()==i-size){
                vessel.pollFirst();
            }
            if(i>=size-1){
                res.add(array[vessel.peekFirst()]);
            }
        }
        return res;
    }
}
